from cmath import inf
from typing import List


class Solution:
    """
    方法：动态规划求解最少硬币数
    
    Args:
        coins: List[int] 可用的硬币面值列表
        amount: int 目标金额
        
    Returns:
        int: 组成目标金额所需的最少硬币个数,如果无法组成则返回-1
        
    Time: O(amount * len(coins)) - 需要遍历每个金额和每个硬币
    
    Space: O(amount) - dp数组大小为amount+1
    """
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0] + [inf] * amount
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[amount] if dp[amount] != inf else -1
        